(1) Field of the Invention
The present invention relates to an apparatus that corrects errors in decoded data. In particular, the invention relates to an apparatus for correcting errors in two-dimensional block code at high speed.
(2) Description of the Prior Art
When a data storage device uses a magnetic or optical disc as a storage medium, scratches or dirt on the disc can cause data errors. To enable such errors to be corrected, codes specifically for this purpose are added when recording data onto the storage medium. These codes are commonly called error correction codes or parity data. During the reproduction of recorded data, errors are detected using the error correction codes and the detected errors are corrected. Hereafter, the processing for adding these error correction codes and the processing for correcting errors will collectively be called "error-related processing". To improve the performance of error-related processing, many systems use Reed-Solomon codes as the error correction codes and product code as the data structure.
FIG. 1 shows an example of product code. Information composed of k1*k2 bytes is assigned ml bytes of parity data in the horizontal (row) direction (hereinafter the "C1 series" or "C1 direction") and m2 bytes of parity data in the vertical (column) direction (hereinafter the "C2 series" or "C2 direction"). The combination of the information, the C1 parity data and the C2 parity data compose one block. This block is the largest unit for which error correction can be performed. This block is n1*n2 bytes in size. Usually, the information and the parity data will be stored in a memory such as a DRAM (Dynamic Random Access Memory) by incrementing the address in the memory by one in the C1 direction. As a result, the data that composes the code sequences in the C1 direction is stored in storage areas with consecutive addresses. Conversely, the code sequences in the C2 direction is stored in storage areas with non-consecutive addresses. Note that the separate codes that compose the product data will be called "data" or "data elements" in the following explanation.
FIG. 2 shows the flow of the error correction performed for the code sequences in the C1 direction. Error correction is first performed for the code sequence in the first row. The processing then proceeds to the second and following rows and is repeated a total of n.sub.2 times. This means that data is scanned and error correction is performed for one entire row at a time. The term "scan" here also refers to the reading order used when reading the data that is to be subjected to error detection and error correction from the storage areas. In this text, the term "error detection" refers to processing that does not include error correction. The term "error correction" meanwhile can refer both to error correction and to the error detection that precedes it.
FIG. 3 shows the flow of the error correction performed on the C2 code sequences. Error correction is first performed for the code sequence in the first column. The processing then proceeds to the second and following columns and is repeated a total of n.sub.1 times. This means that data is scanned and error correction is performed for one entire column at a time.
FIG. 4 is a block diagram showing the composition of a conventional error correction apparatus that performs error correction with the flow described above. In this example, there are 100 bytes of information numbered d1 to d100 and 10 bytes of parity data numbered p1 to p10. Together these form one code sequence.
The information and parity data are read from the memory and sequentially inputted into the syndrome generating unit 900. The syndrome generating unit 900 performs a predetermined calculation whenever one data element is inputted and, when all of the information d1.about.d100 and parity data p1.about.p10 that compose one code sequence have been inputted, generates ten syndromes. If non-zero data is present in any of these syndromes, this means that an error is present in the code sequence, so that the error position-error value calculating unit 901 uses the syndromes to calculate the error position and the error value. Here, the "error position" is information showing the position of the erroneous data element in the code sequence, while the "error value" shows the size of the error. Finally, the error data updating unit 902 uses the error position and error value to read the error data from the memory and to correct the error, before writing the updated value back into the same position in the memory. This processing is then repeated for another code sequence.
As described above, a conventional error correction apparatus scans and performs error correction one row at a time for code sequences in the C1 direction and one column at a time for code sequences in the C2 direction. In this way, error correction is performed for every code sequence that composes a block.
In recent years, there have been increasing demands for improvements in the processing speed of data storage devices such as modern optical disc drives. Conventional error correction apparatuses, however, are unable to satisfy these demands.
To meet such demands, it would conceivably be possible to use plurality of error correction apparatuses in parallel within a single data storage device. Such an arrangement would however require a large-scale circuit and would reduce cost performance.